HW 11

---

Question 1

• EREW PRAM: Exclusive Read, Exclusive Write Parallel Random Access Machine, where only one processor can write to or read from a memory location in any step.
• CREW PRAM: Concurrent Read, Exclusive Write Parallel Random Access Machine. Similar to EREW, but allows for multiple processors to read from the same memory location concurrently
• CRCW PRAM: Concurrent Read, Concurrent Write Parallel Random Access Machine, where multiple processors can read from and write to the same memory location concurrently.
• List Ranking: An algorithmic technique for efficiently determining the position of each element in a linked list.

Question 2

Initialize:
level[root] = 0
parent[root] = root
for all nodes v != root
    level[v] = infinity
    parent[v] = null

for i = 1 to log e
    for all nodes v
        if ID[v] mod 2^i == 0
            Send level[v] and parent[v] to neighbor ID[v]+2^(i-1)
        else if ID[v] mod 2^i == 2^(i-1)
            Receive level[u] and parent[u] from neighbor ID[v]-2^(i-1)
            if level[u]+1 < level[v]
                level[v] = level[u]+1
                parent[v] = u

We use a CRCW PRAM model here because when a node has more than 1 parent node pointing to it, it should choose arbitrarily who should be its parent. Same for a node pointing to more than 1 child node.

Question 3

Part 1

Function Invocation	Returned Value
Prefix-sum (1,2,3,4,5,6,7,8)	{1,3,6,10,15,21,28,36}
Prefix-sum (1,2,3,4)	{1,3,6,10}
Prefix-sum (5,6,7,8)	{5,11,18,26}
Prefix-sum (1,2)	{1,3}
Prefix-sum(3,4)	{3,7}
Prefix-sum(5,6)	{5,11}
Prefix-sum (7,8)	{7,15}

Part 2

Prefix(X):
    if n = 1
        s = x_1
        return s
    <y_1,...,y_n/2> = Prefix(<x_1,...,x_n/2>)
    <z_1,...,y_n/2> = Prefix(<x_n/2+1,...,x_n>)
    for i from 1 to n parallel do
        if i <= n/2
            s_i = y_i
        else
            s_i = y_n/2 + z_i-n/2
    return s

• Total parallel time: $T(n)=T\left(\frac{n}{2}\right)+O(1)=O(n)$
• Total work done: $W(n)=W\left(\frac{n}{2}\right)+O(n)=O(n)$.

Part 3

Prefix(X):
    if n = 1
        s = x_1
        return s
    <y_1,...,y_n/2> = Prefix(<x_1,...,x_n/2>)
    <z_1,...,y_n/2> = Prefix(<x_n/2+1,...,x_n>)
    send from y_n/2 to z_1
    for i from 1 to log(n/2) parallel do
        send z_1,...,z_2^n correspondly to z_2^n+1,...,z_2^(n+1)
    for i from 1 to n parallel do
        if i <= n/2
            s_i = y_i
        else
            s_i = y_n/2 + z_i-n/2
    return s

• Total parallel time: $T(n)=T\left(\frac{n}{2}\right)+O(\log n)=O\left(\log ^2 n\right)$
• Total work done: $W(n)=W\left(\frac{n}{2}\right)+O(n)=$ $O(n)$